/**
 * 不同路径 2
 *
 * 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
 * 返回机器人能够到达右下角的不同路径数量。
 * 测试用例保证答案小于等于 2 * 109。
 *
 * 示例 1：
 * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：2
 * 解释：3x3 网格的正中间有一个障碍物。
 * 从左上角到右下角一共有 2 条不同的路径：
 * 1. 向右 -> 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右 -> 向右
 *
 * 示例 2：
 * 输入：obstacleGrid = [[0,1],[0,0]]
 * 输出：1
 *
 * 提示：
 * m == obstacleGrid.length
 * n == obstacleGrid[i].length
 * 1 <= m, n <= 100
 * obstacleGrid[i][j] 为 0 或 1
 */

/**
 * 这题上一题一样, 只不过是多了一个障碍物, 我们在 动态求到下一个
 * 位置时, 特别判断一下要是这个位置时障碍, 那么就不进行赋值就可以了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {
    public int uniquePathsWithObstacles(int[][] nums) {

        // 矩阵边长
        int n = nums.length, m = nums[0].length;

        // dp
        int[][] dp = new int[n + 1][m + 1];

        // 初始化
        dp[0][1] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                // 特判
                if (nums[i - 1][j - 1] == 1) {
                    continue;
                } else {

                    // 状态转移
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        // 返回右下角数字
        return dp[n][m];
    }
}